package StringDemo;

/**
 * 给你两个字符串 haystack 和 needle 。
 * 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
 * 如果 needle 不是 haystack 的一部分，则返回  -1 。
 */
public class demo28 {
    public static void main(String[] args) {
        String haystack = "sadsbsadsad";
        String needle = "sadsa";
        System.out.println(strStr(haystack, needle));
        System.out.println(strStrKMP(haystack, needle));
        System.out.println(haystack.indexOf(needle));//现有函数
    }

    // 暴力解法
    public static int strStr(String haystack, String needle) {
        if (needle.length() > haystack.length()) return -1;
        int index = 0;
        while (true) {
            for (int i = 0, j = index; i <= needle.length(); i++, j++) {
                if (i == needle.length()) return index;
                if (j == haystack.length()) return -1;
                if (needle.charAt(i) != haystack.charAt(j)) {
                    index++;
                    break;
                }
            }
        }
    }

    // 完整KMP算法
    public static int strStrKMP(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        // 计算next数组
        //[A,B,A,B,B,A,B,A,B,A,C ] next
        //[0,1,2,3,4,5,6,7,8,9,10] i
        //[0,0,1,2,0,1,2,3,4,3,0 ] k
        // 初始化
        int[] next = new int[m];
        // k为当前最长匹配长度（初始为0）
        for (int i = 1,k = 0; i < m; i++) {
            // 回溯：匹配失败时，缩短匹配长度
            while (k > 0 && needle.charAt(i) != needle.charAt(k)) {
                //当模式串的第 i 个字符（needle[i]）与第 k 个字符（needle[k]）不匹配时，需要「缩短当前的最长匹配长度 k」。
                //如何缩短？通过k = next[k - 1]回溯：next[k-1]是前 k 个字符的最长前缀后缀长度，
                //!!!!!其实就是，因为比如第5个字符匹配值不相等，但前4个已经匹配过了，就找前面四个的最长匹配长度，用其后缀重新做我匹配的前缀
                //如上面例子，next4和next9不一致，但5678和0123一致，所以找其next3长度，推出78和01一致，就缩短了，继续比next2和next9。
                // 利用这个值可以直接跳转到更短的可能匹配位置，避免从头开始比较（这也是 KMP 高效的原因）。
                k = next[k - 1]; // 关键：利用已计算的next值跳转（这里不匹配，你再去最大公共前缀重新找吧）
            }
            // 匹配成功：延长匹配长度
            if (needle.charAt(i) == needle.charAt(k)) {
                k++;
            }
            next[i] = k; // 记录当前最长匹配长度,就是说看next[i]有几个匹配的字符长度了，匹配的越长，k越大
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}
